Ditubuhkan secara rasmi pada tahun 1946 namun rekod mencatatkan Persatuan Bola Sepak Amatur Kelantan sudah wujud seawal tahun 1889, Kelantan FA merupakan pasukan bola sepak tertua di pantai timur Malaysia.

Pada tahun 1986, Timbalan Menteri Besar Kelantan ketika itu, Datuk Haji Ahmad Rastom Haji Ahmad Maher menerajui kepimpinan bola sepak Kelantan sehingga tahun 1990. Pada tahun 1991, Setiausaha Kerajaan Negeri Datuk Haji Wan Hashim Wan Daud mengambil alih kepimpinan yang ditinggalkan oleh Datuk Haji Ahmad Rastom Haji Ahmad Maher setelah tampuk kepimpinan kerajaan negeri bertukar tangan.

Pada tahun 2004, jawatan presiden bertukar tangan setelah Datuk Haji Ahmad Jazlan Yaakub diberi laluan untuk menerajui KAFA. Sejarah tertulis dalam buku bola sepak Kelantan dimana pada tahun 2005, Kelantan merupakan satu-satunya negeri yang bermain dalam Liga FAM setelah berada ditangga tercorot dalam Liga Perdana tahun sebelum itu. Tahun 2007 menyaksikan perubahan dalam lanskap kepimpinan KAFA yang baru apabila Tan Sri Datuk Seri Panglima Haji Annuar Haji Musa diberi kepercayaan menerajui Persatuan Bola Sepak Kelantan bagi penggal 2007/2010.

Tahun pertama Tan Sri bersama Kelantan FA sudah menampakkan peningkatan apabila berjaya meraih tempat ketiga dalam Liga Perdana musim 2007/08. Malahan dalam saingan Piala Malaysia pula, walaupun Kelantan gagal melayakkan diri ke suku akhir Piala Malaysia, tetapi kejutan yang dilakukan diperingkat kumpulan sedikit sebanyak menyaksikan kebangkitan Kelantan tidak harus dipandang rendah.

Pada 2009 Kelantan mampu berbangga kerana berjaya melangkah ke dua final iaitu Final Piala FA dan Final Piala Malaysia. Namun kedua-dua perlawanan menyaksikan hanya bergelar Naib Juara sahaja. Pada 2010 Kelantan akhirnya mencipta sejarahnya tersendiri kerana berjaya mencapai status Naib Juara Liga Super dan Juara Piala Malaysia. Pencapaian Kelantan terus gemilang pada 28 Januari 2011, Kelantan sekali mencipta sejarah buat kali pertama merangkul Piala Sultan Hj Ahmad Shah dengan menewaskan Selangor selaku Juara Bertahan.[2]

Negeri Kelantan Darul Naim tersenarai antara negeri yang mempunyai akademi bola sepaknya sendiri seperti Akademik Bola Sepak Darulnaim yang ditubuhkan oleh kerajaan negeri Kelantan pada tahun 2006 bertujuan mencungkil bakat muda yang berusia 8 hingga 12 tahun. Pada 18 Januari 2008, Presiden KAFA, Tan Sri Annuar Musa berkata bahawa pihaknya akan menubuhkan akademi bola sepak khusus bagi melatih dan menonjolkan bakat semulajadi pemain bawah 13 tahun negeri ini kesinambungan dari Projek Kijang Emas yang diusahakan semasa sekolah rendah oleh Jabatan Pelajaran Negeri. Ia akan ditempatkan di Sekolah Menengah Kebangsaan Chengal itu yang bakal menempatkan 30 orang pelajar. [3]

Kini, mereka menggunakan cogan kata Quputeh, qu puteh, barulah puteh ! sebagai penyunting semangat. Malah, jersi dan juga stadium telah dicat dengan warna merah jambu bagi melambangkan semangat qu puteh, qu puteh, barulah puteh!